package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * tree
 * 2415. 反转二叉树的奇数层
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/18 21:03
 */
public class ReverseOddLevels {

    public TreeNode reverseOddLevels(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        int n = 1;
        while (list.size() >= (1 << n) - 1) {
            int st1 = (1 << (n - 1)) - 1;
            int end1 = (1 << n) - 2;
            boolean f = list.get(st1).left != null;
            for (int i = st1; i <= end1; i++) {
                TreeNode node = list.get(i);
                if (f) {
                    list.add(node.left);
                    list.add(node.right);
                }
            }
            if (f && (n & 1) == 1) {
                int st = end1 + 1;
                int end = (1 << (n + 1)) - 2;
                int m = st + ((end - st) >> 1);
                for (int i = st; i <= m; i++) {
                    int item = list.get(i).val;
                    list.get(i).val = list.get(st + end - i).val;
                    list.get(st + end - i).val = item;
                }
            }
            n++;
        }
        return root;
    }


}
